import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

/**
 * @Author 12629
 * @Description：
 */
public class Test {

    public static void main1(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        List<Integer> linkedList = new LinkedList<>(arrayList);

        System.out.println(linkedList);

        System.out.println("==========");
        for(Integer x : linkedList) {
            System.out.print(x+" ");
        }
        System.out.println();
        //System.out.println(linkedList.get(2));
        System.out.println("==========");
        ListIterator<Integer> lit = linkedList.listIterator();
        while (lit.hasNext()) {
            System.out.print(lit.next()+" ");
            //lit.remove();
        }//???? 思考：这个迭代器的工作原理
        // 作业2：能不能 一边遍历 一边删除？？ 可以删除会发生什么问题？ 不可以删除会发生什么问题？
        System.out.println();

        System.out.println("==========");
        ListIterator<Integer> lit2 =  linkedList.listIterator(linkedList.size());
        while (lit2.hasPrevious()) {
            System.out.print(lit2.previous()+" ");
        }
        System.out.println();
    }


    public static void main3(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.display();
        /*myLinkedList.removeAllKey(30);
        myLinkedList.display();*/
        myLinkedList.clear();
        System.out.println("=====");
    }

    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1,MySingleList.ListNode list2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmpH = newHead;
        while(list1 != null && list2 != null) {
            if(list2.val < list1.val) {
                tmpH.next = list2;
                tmpH = tmpH.next;
                list2 = list2.next;
            }else{
                tmpH.next = list1;
                tmpH = tmpH.next;
                list1 = list1.next;
            }
        }
        if(list1 != null) {
            tmpH.next = list1;
        }
        if(list2 != null) {
            tmpH.next = list2;
        }
        return newHead.next;
    }

    public MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA,
                                                     MySingleList.ListNode headB) {

        MySingleList.ListNode plong = headA;//假设A长
        MySingleList.ListNode pshort = headB;

        //1、分别求两个链表的长度
        int len1 = 0;
        int len2 = 0;
        //O(M)
        while (plong != null) {
            len1++;
            plong = plong.next;
        }
        //O(N)
        while (pshort != null) {
            len2++;
            pshort = pshort.next;
        }
        plong = headA;
        pshort = headB;
        //2、求差值步的len
        int len = len1 - len2;
        if(len < 0) {
            plong = headB;
            pshort = headA;
            len = len2 - len1;
        }
        //plong 一定指向最长的链表  pshort一定指向最短的链表  len一定是一个正数
        //3、哪个链表长 走len步
        while (len != 0) {
            plong = plong.next;
            len--;
        }
        //4、一起走 直到相遇！
        while (plong != pshort) {
            plong = plong.next;
            pshort = pshort.next;
        }
        return plong;
    }

    public static void main2(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(23);
        mySingleList1.addLast(34);
        mySingleList1.addLast(45);
        mySingleList1.addLast(56);


        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(15);
        mySingleList2.addLast(20);
        mySingleList2.addLast(25);
        mySingleList2.addLast(55);
        mySingleList2.addLast(156);

        MySingleList.ListNode ret = mergeTwoLists(mySingleList1.head,mySingleList2.head);

        mySingleList1.show(ret);



    }
    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        //mySingleList.createList();

        mySingleList.addLast(12);
        mySingleList.addLast(23);
        mySingleList.addLast(34);
        mySingleList.addLast(45);
        mySingleList.addLast(56);
        //mySingleList.show3(mySingleList.head);

        mySingleList.show4();
      /*  MySingleList.ListNode ret = mySingleList.findKthToTail(3);
        System.out.println(ret.val);*/

        /*MySingleList.ListNode ret = mySingleList.reverseList();
        mySingleList.show(ret);*/




        /*mySingleList.removeAllKey(12);
        System.out.println("删除所有的key：");
        mySingleList.show();

        mySingleList.addLast(99);
        mySingleList.show();
        try {
            mySingleList.addIndex(3,199);
        }catch (IndexOutOfBounds indexOutOfBounds) {
            indexOutOfBounds.printStackTrace();
        }
        mySingleList.show();*/

        /*System.out.println(mySingleList.size());
        System.out.println(mySingleList.contains(12));
        System.out.println(mySingleList.contains(34));
        System.out.println(mySingleList.contains(56));
        System.out.println(mySingleList.contains(156));*/
    }
}
